// 给定一个单链表L的头节点head， 0,1,2,3,4.....n-1,n , 要求将单链表重新排列，0,n,1,n-1,2,n-2.....

// 思路：双指针，将链表转为数组，从新链接的时候需要判断当left === right的时候跳出循环,并把left节点的next置为空
// 时间复杂度：O(n)，n是链表的节点数
// 空间复杂度：O(n)

const { LinkedList, ListNode} = require('./64.设计链表')
function reorderList(head) {
    let arr = []
    let cur = head
    while (cur) {
        arr.push(cur)
        cur = cur.next
    }
    let left = 0
    let right = arr.length - 1
    while (left < right) {
        arr[left].next = arr[right]
        left++
        if (left === right) {
            break
        }
        arr[right].next = arr[left]
        right--
    }
    arr[left].next = null
    return head
}

let node = new LinkedList([1,2,3,4,5,6,7])
reorderList(node.head)
console.log(node.head)